// https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 哈希表记录每个连续区间的边界长度
// 2. 动态更新区间两端点的长度信息
// 3. 新元素连接相邻区间时合并长度
// 4. 避免重复处理已存在元素
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <unordered_map>

class Solution 
{
public:
    int longestConsecutive(vector<int>& nums) 
    {
        int m = nums.size();
        unordered_map<int, int> hash;

        for (const int& num : nums)
        {
            int prev = (hash.find(num - 1) == hash.end() ? 0 : hash[num - 1]);
            int next = (hash.find(num + 1) == hash.end() ? 0 : hash[num + 1]);
            if (hash.count(num) == 0)
            {
                hash[num] = prev + next + 1;
                if (prev > 0)
                    hash[num - prev] = hash[num];
                if (next > 0)
                    hash[num + next] = hash[num];
            }
        }

        int ret = 0;
        for (const auto& [x, y] : hash)
        {
            ret = max(ret, y);
        }

        return ret;
    }
};

int main()
{
    vector<int> nums1 = {100,4,200,1,3,2};
    vector<int> nums2 = {0,3,7,2,5,8,4,6,0,1};

    Solution sol;

    cout << sol.longestConsecutive(nums1) << endl;
    cout << sol.longestConsecutive(nums2) << endl;

    return 0;
}